package niuke;

import java.util.Arrays;
import java.util.Random;

/**
 * Created by asus on 2017/11/29.
 */
public class Bags01 {
    int n = 10;
    int capacity = 150;
    int[] weight;
    int[] value;
    public int maxValue = 0;
    int tempValue;
    int tempWeight;
    int[] way = new int[n];
   public int[] bestWay = new int[n];

    public Bags01(int[] weight, int[] value) {
        this.weight = weight;
        this.value = value;
    }

    public void backTrack(int t){
        //已经搜索到根节点
        if(t>n-1){
            if(tempValue > maxValue){
                maxValue = tempValue;
                for(int i=0;i<n;i++)
                    bestWay[i] = way[i];
            }
            return;
        }
        //搜索左边节点
        if(tempWeight + weight[t] <= capacity){
            tempWeight += weight[t];
            tempValue += value[t];
            way[t] = 1;
            backTrack(t+1);
            tempWeight -= weight[t];
            tempValue -= value[t];
            way[t] = 0;
        }
        //不装入这个物品，直接搜索右边的节点
        if( bound(t+1) >= maxValue){
            backTrack(t+1);
        }
    }
    //用于计算剩余物品的最高价值上界
    public double bound(int k){
        double maxLeft = tempValue;
        int leftWeight = capacity - tempWeight;
        //尽力依照单位重量价值次序装剩余的物品
        while(k <= n-1 && leftWeight > weight[k] ){
            leftWeight -= weight[k];
            maxLeft += value[k];
            k++;
        }
        //不能装时，即leftWeight < weight[k]，但此时并不能确保该物品之后就没有可选的了
        // 用下一个物品的单位重量价值折算到剩余空间作为推测。
        if( k <= n-1){
            maxLeft += value[k]/weight[k]*leftWeight;
        }
        return maxLeft;
    }

    public static void main(String[] args){
        int count=3;
        while(count-->0) {
            Random random = new Random();
            int[] weight = new int[10];
            int[] value = new int[10];
            for (int i = 0; i < 10; i++) {
                weight[i] = random.nextInt(40)+1;
                value[i] = random.nextInt(50)+1;
            }
            double[] temp=new double[10];
            for(int i=0;i<10;i++){
                temp[i]=value[i]/(weight[i]*1.0);
            }
            System.out.println();
            //在测试前，必须先对物品进行按单位价值降序排列！，因为剪枝函数的逻辑要求
            for (int i = 0;i <10;i++){
                for(int j = i;j <10;j++){
                    if (temp[i] < temp[j]){
                        double a = temp[i];
                        temp[i]=temp[j];
                        temp[j]=a;
                        int t = weight[i];
                        weight[i]=weight[j];
                        weight[j]=t;
                        int y=value[i];
                        value[i]=value[j];
                        value[j]=y;
                    }
                }
            }
            Bags01 b = new Bags01(weight, value);
            long startTime = System.nanoTime();   //获取开始时间
            b.backTrack(0);
            long endTime = System.nanoTime();    //获取结束时间
            System.out.println("weight[]: "+ Arrays.toString(weight));
            System.out.println("value[]: "+Arrays.toString(value));
            System.out.println("cost:" + (endTime - startTime) + " ns");
            System.out.println("该背包能够取到的最大价值为:" + b.maxValue);
            System.out.println("取出的方法为:");
            for (int i : b.bestWay)
                System.out.print(i + "  ");
            System.out.println();
        }
    }
}
